#pragma once

#include <stack>
#include <queue>
using namespace std;

#include <iostream>
#include <vector>
using namespace std;

struct Data
{
    char ch; // 编号
    int _val;
};

class TreeNode
{
public:
    Data _data;
    TreeNode *_left;
    TreeNode *_right;

public:
    TreeNode(Data data)
        : _data(data), _left(nullptr), _right(nullptr)
    {
    }
};

class My_Tree
{
public:
    My_Tree()
        : root(nullptr)
    {
    }

    // 通过前序构造二叉树
    // TreeNode *BinaryTreeCreate(vector<Data> &data, int &i)
    // {
    //     if (i >= data.size() || data[i].ch == '#')
    //     {
    //         ++i;
    //         return nullptr;
    //     }

    //     TreeNode *root = new TreeNode(data[i]);
    //     ++i;
    //     root->_left = BinaryTreeCreate(data, i);
    //     root->_right = BinaryTreeCreate(data, i);

    //     return root;
    // }

    // 前序
    void _BianryTreePreOrder(TreeNode *root)
    {
        if (root == nullptr)
        {

            return;
        }
        cout << "(" << root->_data.ch << "-" << root->_data._val << ")->";
        _BianryTreePreOrder(root->_left);
        _BianryTreePreOrder(root->_right);
    }

    void _BianryTreeInOrder(TreeNode *root)
    {
        if (root == nullptr)
        {

            return;
        }

        _BianryTreeInOrder(root->_left);
        cout << "(" << root->_data.ch << "-" << root->_data._val << ")->";
        _BianryTreeInOrder(root->_right);
    }

    // 后序
    void _BianryTreePostOrder(TreeNode *root)
    {
        if (!root)
        {

            return;
        }
        _BianryTreePostOrder(root->_left);
        _BianryTreePostOrder(root->_right);
        cout << "(" << root->_data.ch << "-" << root->_data._val << ")->";
    }

    void _BianrytreeLevelOrder(TreeNode *root)
    {
        queue<TreeNode *> q;
        if (root)
        {
            q.push(root);
        }
        while (!q.empty())
        {
            auto node = q.front();
            q.pop();
            cout << "(" << node->_data.ch << "-" << node->_data._val << ")->";
            if (node->_left)
                q.push(node->_left);
            if (node->_right)
                q.push(node->_right);
        }
    }

    void BianryTreePreOrder()
    {
        cout << "递归前序遍历  #";

        _BianryTreePreOrder(root);
        cout << endl;
    }

    void BianryTreeInOrder()
    {
        cout << "递归中序遍历  #";

        _BianryTreeInOrder(root);
        cout << endl;
    }
    void BianrytreeLevelOrder()
    {
        cout << "非递归层序遍历 #";

        _BianrytreeLevelOrder(root);
        cout << endl;
    }
    void BianryTreePostOrder()
    {
        cout << "递归后序遍历  #";
        _BianryTreePostOrder(root);
        cout << endl;
    }

    // 非递归
    void _BianryTreeNonPre(TreeNode *root)
    {
        stack<TreeNode *> st;
        st.push(root);
        while (!st.empty())
        {
            auto node = st.top();
            st.pop();
            cout << "(" << node->_data.ch << "-" << node->_data._val << ")->";
            if (node->_right)
                st.push(node->_right);
            if (node->_left)
                st.push(node->_left);
        }
    }

    void BianryTreeNonPre()
    {
        cout << "非递归前序遍历#";
        _BianryTreeNonPre(root);
        cout << endl;
    }

    vector<vector<Data>> vv;

    void _LeverTraversal(TreeNode *root, int layer)
    {
        if (root)
        {
            if (vv.size() == layer)
            {
                vv.push_back(vector<Data>());
            }
            vv[layer].push_back(root->_data);

            if (root->_left)
                _LeverTraversal(root->_left, layer + 1);

            if (root->_right)
                _LeverTraversal(root->_right, layer + 1);
        }
    }

    void LevelOrderTraversal()
    {
        _LeverTraversal(root, 0);
        cout << "递归的层序遍历#";
        for (int i = 0; i < vv.size(); i++)
        {
            for (int j = 0; j < vv[i].size(); j++)
            {
                cout << "(" << vv[i][j].ch << ":" << vv[i][j]._val << ")->";
            }
        }
        cout << endl;
    }

    // 非递归 一直放左孩子，空则出栈
    void _BianryTreeNonInOrder(TreeNode *root)
    {
        stack<TreeNode *> st;
        TreeNode *node = root;
        while (node || !st.empty())
        {
            while (node)
            {

                st.push(node);
                node = node->_left;
            }
            if (!st.empty())
            {
                node = st.top();
                st.pop();
                cout << "(" << node->_data.ch << "-" << node->_data._val << ")->";
                node = node->_right;
            }
        }
    }

    void BianryTreeNonInOrder()
    {
        cout << "非递归中序遍历#";
        _BianryTreeNonInOrder(root);
        cout << endl;
    }

    // prev是他的右 左孩子
    void _BinaryTreeNonPost(TreeNode *root)
    {
        if (!root)
            return;

        stack<TreeNode *> st;
        TreeNode *current = root;
        TreeNode *prev = nullptr;

        while (current || !st.empty())
        {
            // 取出左
            while (current)
            {
                st.push(current);
                current = current->_left;
            }

            // 右为空  遍历左，记录当前
            current = st.top();
            if (!current->_right || current->_right == prev)
            {
                cout << "(" << current->_data.ch << "-" << current->_data._val << ")->";
                st.pop();
                prev = current;
                current = nullptr;
            }
            else
            {
                current = current->_right;
            }
        }
    }
    void BainaryTreeNonPost()
    {
        cout << "非递归后序遍历#";
        _BinaryTreeNonPost(root);
        cout << endl;
    }
    ////////////////////////////////////搜索
    bool _DfsPrevOder(TreeNode *root, int target, vector<Data> &path)
    {
        if (!root)
            return false;
        path.push_back(root->_data);
        if (root->_data._val == target)
            return true;

        if (_DfsPrevOder(root->_left, target, path) || _DfsPrevOder(root->_right, target, path))
            return true;

        // 没找到
        path.pop_back();
        return false;
    }

    void DfsPrevOder(int target)
    {
        cout << "前序查找val:" << target;
        vector<Data> path;
        if (_DfsPrevOder(root, target, path))
        {
            cout << "   找到啦！"
                 << "遍历的结果是";
            for (auto x : path)
            {
                cout << "(" << x.ch << ":" << x._val << ")";
            }
            cout << endl;
        }
        else
        {
            cout << "  没有找到" << endl;
        }
    }

    // 后序搜索
    bool _DfsPostOrder(TreeNode *root, int target, vector<Data> &path)
    {
        if (!root)
            return false;

        stack<TreeNode *> st;
        TreeNode *current = root;
        TreeNode *lastVisited = nullptr;

        while (current || !st.empty())
        {
            if (current)
            {
                st.push(current);
                current = current->_left;
            }
            else
            {
                TreeNode *peekNode = st.top();
                if (!peekNode->_right || peekNode->_right == lastVisited)
                {
                    lastVisited = peekNode;
                    st.pop();
                    if (peekNode->_data._val == target)
                    {
                        path.push_back(peekNode->_data);
                        return true;
                    }
                }
                else
                {
                    current = peekNode->_right;
                }
            }
        }
        return false;
    }

    void DfsPostOrder(int target)
    {
        cout << "后序查找val:" << target;
        vector<Data> path;
        if (_DfsPostOrder(root, target, path))
        {
            cout << "   找到啦！遍历的路径是";
            for (auto it = path.rbegin(); it != path.rend(); ++it)
            {
                cout << "(" << it->_val << ":" << it->ch << ") ";
            }
            cout << endl;
        }
        else
        {
            cout << "  没有找到" << endl;
        }
    }

    void _BinarytreeLevelOrderSearch(TreeNode *root, int target, vector<Data> &path)
    {
        queue<TreeNode *> q;
        if (root)
        {
            q.push(root);
        }
        while (!q.empty())
        {
            auto node = q.front();
            path.push_back(node->_data);
            q.pop();
            if (node->_data._val == target)
                break;
            if (node->_left)
                q.push(node->_left);
            if (node->_right)
                q.push(node->_right);
        }
    }

    void BinarytreeLevelOrderSearch(int target)
    {
        cout << "层序查找val:" << target;
        vector<Data> path;
        _BinarytreeLevelOrderSearch(root, target, path);
        if (!path.empty() && path.back()._val == target)
        {
            cout << "   找到啦！遍历的路径是";
            for (auto it = path.begin(); it != path.end(); ++it)
            {
                cout << "(" << it->_val << ":" << it->ch << ") ";
            }
            cout << endl;
        }
        else
        {
            cout << "  没有找到" << endl;
        }
    }

public:
    TreeNode *root;
};
